package leetcode_ago.string_and_array;

/**
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法
 * 思路：
 * 遍历排序数组：二分查找
 * 相等返回下标，不相等返回会被插入的位置（循环结束的条件是left>right，此时的left就是未找到并且是待插入位置）
 * 注意target小于最小值(可以并在Index中)和大于最大值的情况（最大要在末尾length出加）
 */
public class Num35_SearchInsert1 {
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        if(target>nums[right]){
            return nums.length;
        }
        while (left<=right){
            int mid=(right-left)>>1+left;
            if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                return mid;
            }
        }
        //走到这里target并未被找到，left此时就是需要返回的下标
        return left;
    }
}
